package com.warningrc.demo;

import java.util.ArrayList;
import java.util.Stack;


public class DFS_4 {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }

    // 寻找图中两点之间简单路径的方法，接受起始节点和目标节点作为参数
    public static ArrayList<Integer> findPath(Node start, Node end) {
        // 创建一个栈来辅助深度优先搜索
        Stack<Node> stack = new Stack<>();
        // 创建一个列表来存储路径
        ArrayList<Integer> path = new ArrayList<>();
        // 创建一个布尔数组来标记节点是否被访问，假设图中最多有100个节点，根据实际情况调整大小
        boolean[] visited = new boolean[100];
        // 调用辅助方法进行深度优先搜索寻找路径
        findPathUtil(start, end, stack, path, visited);
        return path;
    }

    // 辅助的深度优先搜索方法，用于寻找从起始节点到目标节点的路径
    private static boolean findPathUtil(Node current, Node end, Stack<Node> stack, ArrayList<Integer> path, boolean[] visited) {
        // 将当前节点压入栈
        stack.push(current);
        // 标记当前节点为已访问
        visited[current.value] = true;
        // 如果当前节点是目标节点
        if (current == end) {
            // 将栈中的节点值添加到路径列表中
            for (Node node : stack) {
                path.add(node.value);
            }
            return true;
        }
        // 遍历当前节点的邻接节点
        for (Node neighbor : current.neighbors) {
            // 如果邻接节点未被访问
            if (!visited[neighbor.value]) {
                // 递归调用寻找路径方法
                if (findPathUtil(neighbor, end, stack, path, visited)) {
                    return true;
                }
            }
        }
        // 回溯，将当前节点从栈中弹出
        stack.pop();
        return false;
    }
}